/**
 * @Author: lena
 * @Date: 2021/9/24 20:32
 * @Description: 双向链表
 * @Version: 1.0.0
 */

package data_structure

// DoubleListNode 定义双向链表
type DoubleListNode struct {
    val int
    pre *DoubleListNode
    next *DoubleListNode
}

// NewDoubleListNode 创建节点
func NewDoubleListNode(val int) *DoubleListNode {
    return &DoubleListNode{
        val: val,
        pre: nil,
        next: nil,
    }
}

// pre 返回前驱节点
func pre(head *DoubleListNode,node *DoubleListNode) (bool,*DoubleListNode) {
    if head==nil || head==node {
        return false,nil
    }
    return true, node.pre
}

// del 删除节点
func del(head *DoubleListNode,node *DoubleListNode) (bool,*DoubleListNode) {
    if head == nil {
        return false,nil
    }
    if head == node {
        return true,head.next
    }
    // 获取上一个节点
    p:=node.pre
    // 删除节点
    p.next=node.next
    p.next.pre=p
    // 断开
    node.pre=nil
    node.next=nil
    return true,head
}

// insert 插入节点：在最后插入
func insert(head *DoubleListNode,node *DoubleListNode) (bool,*DoubleListNode) {
    if head == nil {
        return true,node
    }
    p:=head
    for p.next != nil {
        p=p.next
    }
    // p指向最后一个节点
    p.next=node
    node.pre=p
    return true,head
}

// update 修改节点
func update(head *DoubleListNode,node *DoubleListNode,new *DoubleListNode) (bool,*DoubleListNode) {
    if head == nil {
        return true, node
    }
    // 找到node节点
    p:=head
    for p!=nil {
        // 找到要修改的节点
        if p == node {
            // 删除该节点，使用new节点替换
            p1:=p.pre
            p2:=p.next
            p1.next=new
            new.next=p2
            new.pre=p1
            p2.pre=new
            // 断开node的链接
            node.pre=nil
            node.next=nil
            return true,head
        }
        p=p.next
    }
    return false,head
}

// each 遍历节点：怎么动态存数组
func each(head *DoubleListNode) []int {
    res := make([]int,0)
    p := head
    for p!=nil {
        res=append(res, p.val)
        p=p.next
    }
    return res
}